-- file: ch04/myFoldl.hs

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
  where
    step x g a = g (f a x)

-- 关键在于, foldr 返回的结果可以不是 常数，可以是函数
-- 如下:
-- foldr step id xs z
-- haskell 左结合, 理解成 foldr step id xs 返回一个函数，再作用到 z 上,

-- let xs=(x0:xs0), :> foldr step id (x0:xs0) z
-- 等价于
-- step x0 (foldr step id xs0) z
-- 它是递归的, 所以当前只要实现 f(z x0), 放到 z 的位置上, z 是初始值
-- (foldr step id xs0) (f z x0)

-- 令 xs0 = x1:xs1, f z x = t
-- step x1 (foldr step id xs1) t
-- (foldr step id xs1) (f t x1)

-- 一直到最后一步, 返回 id 函数,
-- (foldr step id []) z
-- id z = z

-- 验证 myFoldL 的展开
f x y = "[" ++ show x ++ "," ++ show y ++ "]"

testMyFoldl = myFoldl f "0" [1 .. 5]